package leetcodev1.链表;

import java.util.HashSet;
import java.util.Set;

public class LeetCode141 {

    //用快慢指针同时走，如果相遇则有环
    public boolean hasCycle(ListNode head) {
        ListNode slowIndex = head, quickIndex = head.next;
        while (quickIndex != null) {
            if (slowIndex == quickIndex) {
                return true;
            }

            slowIndex = slowIndex.next;
            quickIndex = quickIndex.next.next;//quickIndex.next可能已经是null需要注意边界
        }
        return false;
    }
}

class Answer141{
    //快慢指针处理 时间复杂度o(n) 空间复杂度0
    public boolean hasCycle(ListNode head) {
        //处理异常 next含有null则肯定不是环形链表
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

    //hash表 时间复杂度o(n) 空间复杂度n
    public boolean hasCycle1(ListNode head) {
        Set<ListNode> seen = new HashSet<ListNode>();
        while (head != null) {
            if (!seen.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }
}
